class Solution {
public:
    vector<int> sortArrayByParity(vector<int>& nums) {
        int n=nums.size(), odd=0, even=n-1;
        while(true)
        {
            while(even>=0&&nums[even]%2) even--;//找到待排数组中的最右侧偶数
            if(even==n) break;
            while(odd<n&&nums[odd]%2==0) odd++; //找到待排数组中的最左侧奇数
            if(odd==n) break;
            if(even>odd) swap(nums[odd], nums[even]);
            else break;
            
        }
        return nums;
    }
};